class Solution {
    bool findTarget(vector<int> &nums, int target)
    {
        unordered_set<int> hash;
        hash.insert(0);
        for(int &x : nums)
        {
            int tmp = target - x;
            if(hash.count(tmp))
                return true;
            hash.insert(x);
        }
        return false;
    }
public:
    int maxSumDivThree(vector<int>& nums) {
        // 以下是贪心解法
        int sum = 0;
        for(int &x : nums)    
            sum += x;
        if(sum % 3 == 0)
            return sum;

        // 分情况讨论
        // 预处理，统计nums中mod3之后为1和2的元素，并且按从小到大排序
        vector<int> a[3];
        for(int &x : nums)
            a[x % 3].push_back(x);
        sort(a[1].begin(), a[1].end());
        sort(a[2].begin(), a[2].end());

        // 1. sum % 3 == 1;
        // 如果a[1]不为空，返回结果有可能是sum - a[1][0]
        // 如果a[2]至少有俩数，结果有可能是sum - a[2][0] - a[2][1];

        // 2. sum % 3 == 2
        // 如果a[2]不为空，返回结果有可能是sum - a[2][0]
        // 如果a[1]至少有俩数，结果有可能是sum - a[1][0] - a[1][1];
        // 如果 smod3=2，那么可以交换数组 a[1] 和 a[2]，从而复用同一套逻辑
        if(sum % 3 == 2)
            swap(a[1], a[2]);
            
        int ans = a[1].size() > 0 ? sum - a[1][0] : 0;
        if(a[2].size() > 1)
            ans = max(ans, sum - a[2][0] - a[2][1]);

        return ans;

        // 下面这种是B站网友解法
        // 求出数组和，再求%3之后的余数
        // sum - (余数 + k * 3)，k的取值从0开始，直到这个表达式结果能被3整除
    
        // int sum = 0;
        // for(int &x : nums)
        //     sum += x;
        // int remain = sum % 3;
        // while(sum % 3 != 0)
        // {
        //     if(findTarget(nums, remain))
        //         sum -= remain;
        //     else
        //         remain += 3;
        // }
        // return sum;
    }
};